#include <bits/stdc++.h>
using namespace std;

#define uLL unsigned long long

#define isD(c) ((c) >= '0' && (c) <= '9')
#define isX(c) ((c) >= 'A' && (c) <= 'Z')

uLL T38[11] = {
    6278211847988224,
    165216101262848,
    4347792138496,
    114415582592,
    3010936384,
    79235168,
    2085136,
    54872,
    1444,
    38,
    1,
};

uLL T26[6] = {
    6327360,
    175760,
    17576,
    676,
    26,
    1,
};

unordered_map<uLL, pair<string, uLL>> mCache12;
unordered_map<uLL, pair<string, uLL>> mCache25;
uLL timeStep = 0;

void getCache(uLL hashV, int type, string &store)
{
    auto &mCache = type == 12 ? mCache12 : mCache25;
    if (mCache.count(hashV))
    {
        store = "#" + mCache[hashV].first;
        return;
    }
    store = "###";
}

void setCache(uLL hashV, int type, string &code)
{
    auto &mCache = type == 12 ? mCache12 : mCache25;
    mCache[hashV] = {code, timeStep++};
}

inline bool isSpe(string &s)
{
    if (s.size() < 5 || s.size() > 6)
        return false;
    int n = s.size();
    return (
        isX(s[n - 1]) &&
        isX(s[n - 2]) &&
        isX(s[n - 3]) &&
        isD(s[n - 4]) &&
        (isX(s[n - 5]) || isD(s[n - 5])) &&
        (isX(s[0]) || isD(s[0])));
}

inline uLL speToNum(string &s)
{
    assert(s.size() == 5 || s.size() == 6);
    int st = 0, ti = 1;
    uLL res = 0;
    // 1
    uLL num = 0;
    char c;
    if (s.size() == 6)
    {
        c = s[st++];
        if (c == ' ')
            num = 0;
        else if (isD(c))
            num = 1 + c - '0';
        else if (isX(c))
            num = 11 + c - 'A';
        else
            assert(false);
        res += num * T26[0];
    }
    // 2
    c = s[st++];
    if (isD(c))
        num = c - '0';
    else if (isX(c))
        num = (c - 'A' + 10);
    else
        assert(false);
    res += num * T26[ti++];
    // 3
    c = s[st++];
    if (isD(c))
        num = (c - '0');
    else
        assert(false);
    res += num * T26[ti++];
    // 4 - 6
    for (int hh = 4; hh <= 6; ++hh)
    {
        c = s[st++];
        if (isX(c))
            num = (c - 'A');
        else
            assert(false);
        res += num * T26[ti++];
    }
    return res;
}

inline uLL norToNum(string &s)
{
    uLL num = 0;
    int i = 0;
    uLL res = 0;
    for (auto c : s)
    {
        if (c == '_')
            num = 37;
        else if (isX(c))
            num = (c - 'A' + 11);
        else if (isD(c))
            num = (c - '0' + 1);
        else if (c == ' ')
            num = 0;
        else
            assert(false);
        res += num * T38[i++];
    }
    return res;
}

inline uLL bitToNum(string &origin, int st, int len)
{
    uLL res = 0;
    int en = st + len;
    for (int i = st; i < en; ++i)
        res = (res << 1) + (origin[i] - '0');
    return res;
}

inline uLL toHashVal(uLL num, int n)
{
    const uLL multiplier = 47055833459ULL; // 2^35 极限情况会爆ULL -> 2^93左右

    if (num > ULLONG_MAX / multiplier)
    {
        // 2^32 * 2^32 -> 2^64
        uLL high1 = num >> 32;
        uLL low1 = num & 0xFFFFFFFFULL;

        uLL high2 = multiplier >> 32;
        uLL low2 = multiplier & 0xFFFFFFFFULL;

        uLL a = low1 * low2;
        uLL b = low1 * high2;
        uLL c = high1 * low2;

        // uLL mid = (a >> 32) + (b & 0xFFFFFFFFULL) + (c & 0xFFFFFFFFULL);
        // uLL low = (mid << 32) + (a & 0xFFFFFFFFULL);

        uLL low = a + (((b & 0xFFFFFFFFULL) + (c & 0xFFFFFFFFULL)) << 32);
        return (low >> (64 - n)) % (1ULL << n);
    }
    else
    {
        uLL result = num * multiplier;
        return (result >> (64 - n)) % (1ULL << n);
    }
}

inline void decode28(string &store, uLL codeVal)
{
    store.clear();
    // cache
    if (codeVal < (1ULL << 25))
    {
        getCache(codeVal, 25, store);
        return;
    }
    // spe
    codeVal -= (1ULL << 25);
    uLL codeValCopy = codeVal;
    uLL mod;
    int c;
    int ti = 0;
    // 1
    mod = T26[ti++];
    c = codeValCopy / mod;
    if (c > 36)
        assert(false);
    else if (c > 10)
        store.push_back(char('A' - 11 + c));
    else if (c > 0)
        store.push_back(char('0' - 1 + c));
    codeValCopy %= mod;
    // 2
    mod = T26[ti++];
    c = codeValCopy / mod;
    if (c > 35)
        assert(false);
    else if (c > 9)
        store.push_back(char('A' - 10 + c));
    else
        store.push_back(char(c + '0'));
    codeValCopy %= mod;
    // 3
    mod = T26[ti++];
    c = codeValCopy / mod;
    if (c > 9)
        assert(false);
    else
        store.push_back(char(c + '0'));
    codeValCopy %= mod;
    // 4 - 6
    for (int i = 4; i <= 6; ++i)
    {
        mod = T26[ti++];
        c = codeValCopy / mod;
        if (c > 25)
            assert(false);
        else
            store.push_back(char(c + 'A'));
        codeValCopy %= mod;
    }
}

inline void decode58(string &store, uLL codeVal)
{
    store.clear();
    uLL codeValCopy = codeVal;
    for (int i = 0; i < 11 && codeValCopy; ++i)
    {
        uLL mod = T38[i];
        int c = codeValCopy / mod;
        if (c > 37)
            assert(false);
        else if (c == 37)
            store.push_back('_');
        else if (c > 10)
            store.push_back(char('A' + c - 11));
        else if (c > 0)
            store.push_back(char('0' + c - 1));
        else
            assert(c == 0 && codeValCopy == 0);
        codeValCopy %= mod;
    }
}

inline void saveNumToCache(string &s, uLL num)
{
    uLL hash12 = toHashVal(num, 12);
    uLL hash25 = toHashVal(num, 25);
    setCache(hash12, 12, s);
    setCache(hash25, 25, s);
}

inline void cacheNor(string &s, uLL norNum)
{
    assert(norNum == norToNum(s));
    saveNumToCache(s, norNum);
}

inline void cacheSpe(string &s, uLL speNum)
{
    assert(speNum == speToNum(s));
    uLL norNum = norToNum(s);
    cacheNor(s, norNum);
    // 这里我不理解需不需要再加一个
    // 将speNum->hashVal并存储的？
}

void mSimple(string &s)
{
    uLL accN = bitToNum(s, 1, 28);
    uLL sendN = bitToNum(s, 29, 28);
    uLL placeN = bitToNum(s, 57, 15);
    string acc, send;
    decode28(acc, accN);
    decode28(send, sendN);
    if (acc[0] != '#')
        cacheSpe(acc, accN - (1ULL << 25));
    if (send[0] != '#')
        // 如果最后的消息hashVal相同使用发送方的
        cacheSpe(send, sendN - (1ULL << 25));
    cout << acc << " " << send;
    if (placeN)
        cout << " " << placeN;
    cout << endl;
}

void mComplex(string &s)
{
    uLL firstN = bitToNum(s, 1, 58);
    uLL secondN = bitToNum(s, 59, 12);
    bool isAccFirst = s[71] == '1';
    string first, second;
    decode58(first, firstN);
    getCache(secondN, 12, second);
    if (first[0] != '#')
        cacheNor(first, firstN);
    string &acc = first, send = second;
    if (!isAccFirst)
        swap(acc, send);
    cout << acc << " " << send << endl;
}

void test_speToNum()
{
    string s = "A0BCD";
    uLL num = speToNum(s);
    assert(num == 1758331);
}
void test_norToNum()
{
    string s = "ABCD200_3";
    assert(norToNum(s) == 71101055775146872);
}
void test_toHashVal()
{
    uLL num1 = 71101055775146872;
    assert(toHashVal(num1, 25) == 7770595);
    uLL num2 = 69279249490478336;
    assert(toHashVal(num2, 12) == 909);
}
void test_decode28()
{
    string t;
    decode28(t, 1758331 + (1ULL << 25));
    assert(t == "A0BCD");
}
void test_decode58()
{
    string t;
    decode58(t, 71101055775146872);
    assert(t == "ABCD200_3");
}
void test_SpeAll()
{
    string before = "A0BCD";
    string after;
    decode28(after, speToNum(before) + (1ULL << 25));
    assert(before == after || ((cout << after << endl) && (false)));
    before = "7W7YDL";
    decode28(after, speToNum(before) + (1ULL << 25));
    assert(before == after || ((cout << after << endl) && (false)));
}
void test_NorAll()
{
    string before = "ABCD200_3";
    string after;
    decode58(after, norToNum(before));
    assert(before == after || ((cout << after << endl) && (false)));
    before = "___________";
    decode58(after, norToNum(before));
    assert(before == after || ((cout << after << endl) && (false)));
}
void test_Cache28()
{
    string target = "ZZ9ZZZ";
    uLL speNum = speToNum(target);
    uLL norNum = norToNum(target);
    uLL codeVal = speNum + (1ULL << 25);
    string get28;
    decode28(get28, codeVal);
    assert(target == get28);
    string get58;
    decode58(get58, norNum);
    assert(target == get58);

    uLL hash12 = toHashVal(norNum, 12);
    uLL hash25 = toHashVal(norNum, 25);

    string getHash25Before;
    decode28(getHash25Before, hash25);
    string getHash12Before;
    getCache(hash12, 12, getHash12Before);
    assert(getHash12Before == "###");
    assert(getHash25Before == "###");

    cacheSpe(target, codeVal);

    string getHash25;
    decode28(getHash25, hash25);
    string getHash12;
    getCache(hash12, 12, getHash12);
    assert(getHash12 == "#" + target);
    assert(getHash25 == "#" + target);
}
void simpleTest()
{
    test_norToNum();
    test_speToNum();
    test_toHashVal();
    test_decode28();
    test_decode58();
    test_SpeAll();
    test_NorAll();
    test_Cache28();
}
int main()
{
    // simpleTest(); return 0;
    int n;
    cin >> n;
    while (n--)
    {
        string s;
        cin >> s;
        (s[0] == '0') ? mSimple(s) : mComplex(s);
    }
}
